package xj.graph2d.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/*
 *   Implementation based on Introduction to Algorithms, Cormen, Leiserson, Rivest
 *   Chapter 22, pp. 446-450   
 */
public class DisjointSetForest<X> {

  public DJFNode makeSet(X v) {
    DJFNode<X> node = new DJFNode<X>(v);
    nodes.add(node);
    return node;
  }

  public DJFNode<X> getDJFNode(X x) {
    Iterator<DJFNode<X>> iter = nodes.iterator();
    while (iter.hasNext()) {
      DJFNode<X> n = iter.next();
      if (n.val == x) {
	return n;
      }
    }
    return null;
  }

  public void union(X x, X y) {
    unionDJFNode(getDJFNode(x), getDJFNode(y));
  }

  public void unionDJFNode(DJFNode x, DJFNode y) {
    if (x != null && y != null) {
      link(findSetDJFNode(x), findSetDJFNode(y));
    }
  }

  public X findSet(X x) {
    DJFNode<X> n = findSetDJFNode(getDJFNode(x));
    if (n != null) {
      return n.val;
    } else {
      return null;
    }
  }

  public DJFNode<X> findSetDJFNode(DJFNode<X> x) {
    if (x != null) {
      if (x.parent != x) {
	x.parent = findSetDJFNode(x.parent);
      }
      return x.parent;
    }
    return null;
  }

  protected void link(DJFNode<X> x, DJFNode<X> y) {
    if (x.rank > y.rank) {
      y.parent = x;
    } else {
      x.parent = y;
      if (x.rank == y.rank) {
	y.rank++;
      }
    }
  }

  public Iterator<X> iterator() {
    return new DJFIterator(nodes.iterator());
  }

  public Set<Set<X>> getTrees() {
    DJFNode<X> n1, n2;
    List<DJFNode<X>> reps = new ArrayList<DJFNode<X>>();
    Iterator<DJFNode<X>> iter = nodes.iterator();
    LOOP1: while (iter.hasNext()) {
      n1 = iter.next();
      n1 = findSetDJFNode(n1);
      Iterator<DJFNode<X>> riter = reps.iterator();
      while (riter.hasNext()) {
	n2 = riter.next();
	if (n1 == n2) {
	  continue LOOP1;
	}
      }
      reps.add(n1);
    }

    int n = reps.size();
    Set<X>[] trees = new Set[n];
    int i;
    for (i = 0; i < n; i++) {
      trees[i] = new HashSet();
    }

    iter = nodes.iterator();
    while (iter.hasNext()) {
      n1 = iter.next();
      DJFNode<X> r = findSetDJFNode(n1);
      for (i = 0; i < n; i++) {
	n2 = reps.get(i);
	if (r == n2) {
	  trees[i].add(n1.val);
	  continue;
	}
      }
    }

    Set<Set<X>> result = new HashSet<Set<X>>();
    for (i = 0; i < n; i++) {
      result.add(trees[i]);
    }

    return result;
  }

  Set<DJFNode<X>> nodes = new HashSet<DJFNode<X>>();

  static public class DJFNode<X> {

    public DJFNode(X v) {
      val = v;
      parent = this;
      rank = 0;
    }

    X val;

    DJFNode<X> parent;

    int rank;
  }

  static class DJFIterator<X> implements Iterator<X> {

    public DJFIterator(Iterator<DJFNode<X>> iter) {
      this.iter = iter;
    }

    public boolean hasNext() {
      return iter.hasNext();
    }

    public X next() {
      DJFNode<X> node = iter.next();
      return node.val;
    }

    public void remove() {
      iter.remove();
    }

    Iterator<DJFNode<X>> iter;

  }

}
